package ua.yandex.collections;

import java.util.Comparator;

public class MyCollections {
    
    private static void swap(MyList list, int firstIndex, int secondIndex) {
        Object firstObject = list.get(firstIndex);
        Object secondObject = list.get(secondIndex);
        list.set(firstIndex, secondObject);
        list.set(secondIndex, firstObject);
    }

    /**
     * Reverses the order of the elements in the specified list
     */
    public static void reverse(MyList list) {
        int median = list.size() >> 1;
        for (int firstIndex = 0; firstIndex < median; firstIndex++) {
            swap(list, firstIndex, list.size() - 1 - firstIndex);
        }
    }

    /**
     * Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
     * Если элемент найден, то возвращается его индекс.
     * Если не найдет, то возвращается отрицательное значение,
     * вычисляемое по следующей формуле:
     * (-(insertion point) - 1), где insertion point - индекс
     * того места в массиве,
     * где должен был бы быть указанный элемент.
     */
    public static int binarySearch(MyList list, Object key) {
        int beginOfInterval = 0;
        int endOfInterval = list.size() - 1;
        return intervalBinarySearch(list, key, null,
                beginOfInterval, endOfInterval);
    }

    /**
     * Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
     */
    public static int binarySearch(MyList list, Object key, Comparator cp) {
        int beginOfInterval = 0;
        int endOfInterval = list.size() - 1;
        return  intervalBinarySearch(list, key, cp,
                beginOfInterval, endOfInterval);
    }

    private static int intervalBinarySearch(
            MyList list, Object key, Comparator cp,
            int intervalBegin, int intervalEnd) {
        int begin = intervalBegin;
        int end = intervalEnd;
        if (begin > end) {
            return  -begin - 1;
        }
        int median = (begin + end) >> 1;
        Object middleElement = list.get(median);
        int compare = compare(middleElement, key, cp);
        if (compare > 0) {
            end = median - 1;
        } else if (compare < 0) {
            begin = median + 1;
        } else {
            return median;
        }
        return intervalBinarySearch(list, key, cp, begin, end);
    }

    private static int compare(Object element, Object key, Comparator cp) {
        if (cp == null) {
            return  ((Comparable) element).compareTo(key);
        } else {
            return cp.compare(element, key);
        }
    }
}
